/*
 * @lc app=leetcode.cn id=1219 lang=typescript
 *
 * [1219] 黄金矿工
 */

// @lc code=start
function getMaximumGold(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  let ans = 0;
  const dfs = (i: number, j: number, gold: number): void => {
    gold += grid[i][j];
    ans = Math.max(ans, gold);
    const rec = grid[i][j];
    grid[i][j] = 0;
    for (const [x, y] of dirs) {
      const nx = i + x;
      const ny = j + y;
      if (nx < 0 || nx >= m) continue;
      if (ny < 0 || ny >= n) continue;
      if (grid[nx][ny] === 0) continue;
      dfs(nx, ny, gold);
    }
    grid[i][j] = rec;
  };

  // 枚举每一个起始点
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] == 0) continue;
      dfs(i, j, 0);
    }
  }

  return ans;
}
// @lc code=end
